1. Technical Field
This invention relates to data networks employing node-by-node routing and more particularly, to an improved apparatus and method for identifying and eliminating call looping in such data networks.
2. Description of the Prior Art
In many current data communication arrangements, data is coupled between a network's end-points (such as terminals, personal computers configured as terminals and mainframe computers) via virtual circuits. These virtual circuits are established in response to a destination address contained in the dialing information entered by a user. One such data communication arrangement is the Customer Network Offering (CNO) II, a virtual circuit packet data network based on the DATAKIT.RTM. virtual circuit switch system. This system provides a three-level address that is analogous to a public telephone address and includes an area code, an exchange and a service-name therein. Each level of the address is stored in a routing table in each circuit switch node. The routing table maps an address-level to a trunk-group or a receiving-group that leads to the destination end-point.
Before a call can be established and data transmitted, a virtual circuit must first be set up between the source and the destination in the network. The path taken by the virtual circuit is determined by the routing tables stored in the circuit switch nodes. Once the virtual circuit is set up, all packets of data between the source and destination are transmitted over the path established by the virtual circuit.
In traffic engineering of in-service data networks, network wide measurements are periodically taken to detect service problems. One of the most frequently occurring service problem for data calls is the under utilization of some network components and the over utilization of others. An effective solution to this problem is to divert traffic from the over utilized network components to the under utilized network components. This has the effect of distributing the traffic load more uniformly across the network. In order to effect such rerouting, however, it is necessary to change the routing pattern, i.e., to make changes to the existing routing tables in the circuit switch nodes.
In node-by-node routing networks, making such changes is nontrivial and may introduce errors in the routing tables. Uncorrected errors in the routing tables can cause a number of problems for the network which adversely affect network performance. One such problem is call looping which causes a call to cycle around the same set of nodes during call set-up. A call involved in a loop may eventually break out of the loop and reach its destination, or it may tie up all the virtual circuits available and may have to be retried. In either case, call looping leads to serious network inefficiencies and should be avoided. Another problem is circuitous routing which results in calls being established over paths involving too many hops, i.e., a call passing through too many circuit switch nodes, violating the design constraints. Circuitous routing also leads to network inefficiencies in the form of unacceptably large network delays. Yet another problem resulting from errors in a routing table is dead-end routing which causes some destinations in the network to be unreachable.